As is known in the art, non-invasive diagnosis of coronary artery pathologies has become reality due to the technological advances in image acquisition devices such as the introduction of multi-detector CT. While these advances have definitely improved the image quality significantly, the diagnosis of such pathologies still requires advanced segmentation, quantification and visualization algorithms. Accurate segmentation of coronary arteries is a difficult problem. Specifically, the physical size of coronary arteries is quite small, i.e., their cross-sections often occupy few pixels. Thus, they are much more sensitive to noise and partial voluming effects than other blood vessels. Brightness of vessels decreases significantly along vessels, particularly, at the thinner branches. Presence of nearby bright structures introduces additional difficulties for the segmentation and visualization algorithms.
Numerous vessel segmentation algorithms have been proposed for the segmentation of blood vessels in CE-CTA/MRA, e.g. S. Aylward and E. B. E. Initialization, noise, singularities, and scale in height-ridge traversal for tubular object centerline extraction, IEEE Trans. on Medical Imaging, 21(2):61-75, 2002; K. Krissian, G. Malandain, N. Ayache, R. Vaillant, and Y. Trousset, Model based multiscale detection of 3d vessels, In IEEE Conf. CVPR, pages 722-727, 1998; K. Siddiqi and A. Vasilevskiy, 3d flux maximizing flows, In International Workshop on Energy Minimizing Methods In Computer Vision, 2001; D. Nain, A. Yezzi, and G. Turk, Vessel segmentation using a shape driven flow, In MICCAI, 2004; and O. Wink, W. J. Niessen, and M. A. Viergever, Multiscale vessel tracking, IEEE Trans. on Medical Imaging, 23(1):130-133, 2004. However, relatively fewer segmentation algorithms have specifically focused on coronary arteries (see C. Florin, R. Moreau-Gobard, and J. Williams. Automatic heart peripheral vessels segmentation based on a normal mip ray casting technique. In MICCAI, pages 483-490, 2004 and Y. Yang, A. Tannenbaum, and D. Giddens. Knowledge-based 3d segmentation and reconstruction of coronary arteries using CT images. In Int. Conf. of the IEEE EMBS, pages 1664-1666, 2004).
In general, most segmentation algorithms produce binary vessel map. Since coronaries are very small in size, quantification of pathologies from such maps is susceptible to the errors even in the case of accurate discrete segmentation results. Thus, additional sub-voxel surface modeling is required for accurate quantification. In general, the determination of such vessel models directly from original data is computationally challenging and robustness requires significant engineering efforts.
While accurate detection of coronary cross-sectional boundaries is crucial in stenonis quantification, such boundaries can be also used in constructing of 3D geometric model of coronary arteries. Recently, Tek et. al.(H. Tek, A. Ayvaci, and D. Comaniciu. Multi-scale vessel boundary detection. In Workshop of CVBIA, pages 388-398, 2005) presented a multi-scale model-based method for detecting vessel boundaries very accurately. (U.S. patent application Ser. No. 11/399,164, filed Apr. 6, 2006, entitled “Method and apparatus for detecting vessel boundaries”, inventors Huseyin Tek, Alper Ayvaci and Dorin Comaniciu, published as U.S. Patent Publication 2006/262988 published Nov. 23, 2006, assigned to the same assignee as the present patent application, the subject matter thereof being incorporated herein by reference).
As is also known in the art, minimum mean cycle algorithms have been used for the vessel cross-sectional boundary detection. Recently, Jerymin and Isikawa (see I. Jermyn and H. Ishikawa, Globally optimal regions and boundaries as minimum ratio cycles, IEEE Trans. PAMI, 23(10): 1075-1088, 2001) used this approach on directed graphs for image segmentation. The main idea behind minimum mean cycle algorithm is to find a cycle (contour) in a graph such that its average cost is the minimum. Average cost of a cycle is simply the division of sum of all edge weights on the cycle by its length, the number of edges on the cycle. Mathematically, let G=(V,E) be a graph with n vertices (V) and m weighted edges (E). A cycle, C on G is a path such that it consists of a subset of edges and its first node is the last. The total cost and length of a cycle is the sum of weights, w(C) and sum of lengths, |C| of edges on that cycle, respectively.
Minimum mean cycle algorithm minimizes division of total cost of the cycle by its length, w(C)/|C|. There are several algorithms for implementing the minimum mean cycle algorithm. One such algorithm is referred to as Howard's algorithm described in a paper by J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. M. Gettrick, and J. P. Quadrat. Numerical computation of spectral elements in max-plus algebra. In Conf. on System Structure and Control, 1998) for computationally efficiency, i.e., O(m), and accuracy.